1. Field of the Invention
The present invention relates to decoding of encoded and transmitted data in a communication system, and, more particularly, to decoding algorithms in a turbo decoder.
2. Description of the Related Art
Maximum likelihood (ML) and maximum a posteriori (MAP) algorithms are employed for processing a channel output signal applied to a receiver. ML and MAP algorithms may be used for both detection (to reconstruct estimates for transmitted symbols) and decoding (to reconstruct user data). A ML algorithm, such as a Viterbi algorithm, provides a maximum likelihood estimate of a state sequence of a finite-state, discrete-time Markov process observed in noise. Similarly, a MAP algorithm provides a maximum a posteriori estimate of a state sequence of a finite-state, discrete-time Markov process observed in noise. Both ML and MAP algorithms employ a trellis corresponding to possible states (portion of received symbols or data in the sequence) for each received output channel sample per unit increment in time (e.g., clock cycle).
A trellis diagram may represent states, and transitions between states, of the Markov process spanning an interval of time. The number of bits that a state represents is equivalent to the memory of the Markov process. Probabilities are associated with each state (sometimes called a state metric) and each transition between states (sometimes called a branch metric) within the trellis. Probabilities are also associated with each decision for a sample in the sequence, also referred to as “reliability information”.
A processor implementing a MAP algorithm computes reliability information in the form of log-likelihood ratio (LLR) reliability values Li using α values (forward state probabilities for states in the trellis and also known as a forward state metric or recursion) and β values (reverse state probabilities in the trellis and also known as a backward state metric or recursion), as described subsequently. The α values are associated with states within the trellis, and these α values are stored in memory. The processor using a MAP algorithm then computes values of β and α values are subsequently retrieved from memory to compute the final output LLR values.
A sequence of information bits M={mi}i=0K−1 may be defined, where K is the frame size or block of encoding. An encoder, such as a convolutional encoder of rate r=1/2 and alternate puncturing, may be employed to generate an encoded sequence X={xi,pi}i=0K−1 from M, where xi=mi for a systematic code and pi may be parity (e.g., Hamming code) bits. The encoded sequence X might then be transmitted (e.g., with polarity of bit 0=“1” and bit 1=“−1”) through a channel with additive white Gaussian noise (AWGN) with variance σ2=(No/2) using, for example, binary phase-shift keyed (BPSK) modulation. A receiver may receive a sequence Y={yi,ti}i=0K−1, where yi=xi√{square root over (Eb)}+ni and ti=pi√{square root over (Eb)}+ni, where Eb is the energy of a bit.
Extrinsic information may be generated at the receiver, and may be defined as the sequence Z={zi}i=0K−1, where zi is as given in equation (1):
                                          z            i                    =                      log            ⁢                                          p                ⁡                                  (                                                            m                      i                                        =                                          0                      ⁢                                              |                                            ⁢                      Y                                                        )                                                            p                ⁡                                  (                                                            m                      i                                        =                                          1                      ⁢                                              |                                            ⁢                      Y                                                        )                                                                    ,                            (        1        )            
where p(a=b) is the probability that “a” equals “b”, and the probability of mi, p(mi), is as given in equation (2):
                              p          ⁡                      (                          m              i                        )                          =                                            e                                                m                  i                                ⁢                                                      z                    i                                    /                  2                                                                                    e                                                      -                                          z                      i                                                        /                  2                                            +                              e                                                      z                    i                                    /                  2                                                              .                                    (        2        )            
As described previously, a receiver may form a trellis of states if an ML or MAP decoding algorithm is employed. The variable Si is defined as a state of the trellis (from a set of possible states {Sip}p=0M−1) of the Markov process at time i, yi is defined as the noisy channel output sample at time i corresponding to encoded data, ti is defined as the noisy channel output sample at time i corresponding to the parity bit, and the sample sequence Y is defined as the sequence of length K of noisy channel output samples {yi,ti}i=0K−1.
For a MAP algorithm processing a data block of length K, probability functions at time i may be defined for the Markov process as given in equations (3) through (5):α(Si)=p(Si=s;Y)  (3)β(Si)=p(Y|Si=s)  (4)γ(Si−1,Si)=p(Si=s;Y|Si−1=s′).  (5)where Si is the state of the Markov process variable at time i, Si−1 is the state of the Markov process variable at time i−1, s is the observed state of Si of the Markov process at time i, and s′ is the observed state of Si−1 of the Markov process at time i−1. In equations (3) and (4), p(a|b) is the probability of “a” given the occurrence “b.” The value of α(Si) in equation (3) is a forward state metric (i.e., the probability of being in a state at time i from a given state at time i−1 given the observed sample), and the value of β(Si) in equation (4) is a backward state metric (i.e., the probability of being in a state at time i from a given state at time i+1 given the observed sample). The value of γ(Si−1,Si) is termed a branch metric and is the probability of a transition from a state Si−1 at time i−1 to state Si at time i.
The forward state metric α(Si) and reverse state metric β(Si) are calculated based on a recursive update process, with the initial values set to a predefined value such as 1 or 0 using a priori information. Methods to calculate the branch metric γ(Si−1,Si) are well-known in the art and may be based on a minimized cost function, such as minimum Euclidean distance between the observed channel output yi and the ideal symbol corresponding to yi. State metrics are updated using the previous state metric values and the branch metric values for transitions from the previous states to the current state.
The LLR value Li for a user's symbol at time i may then be calculated as given in equation (6):
                              L          i                =                              log            ⁡                          (                                                p                  ⁡                                      (                                                                  x                        i                                            =                                                                        +                          1                                                ⁢                                                  |                                                ⁢                        Y                                                              )                                                                    p                  ⁡                                      (                                                                  x                        i                                            =                                                                        -                          1                                                ⁢                                                  |                                                ⁢                        Y                                                              )                                                              )                                .                                    (        6        )            
Defining α(Si) and β(Si) from equations (3) and (4) as the forward and backward state metrics at time i, respectively, and defining γ(Si−1,Si) as the branch metric associated with the transition from the state Si−1 at time i−1 to state Si at time i, then the forward recursion for states is given in equation (7):
                                          α            ⁡                          (                              S                i                            )                                =                                    ∑                              S                                  i                  -                  1                                                      ⁢                                          α                ⁡                                  (                                      S                                          i                      -                      1                                                        )                                            ⁢                              γ                ⁡                                  (                                                            S                                              i                        -                        1                                                              ,                                          S                      i                                                        )                                                                    ,                            (        7        )            where the summation is over all transitions from state Si−1 at time i−1 to state Si at time i which are valid transitions. In general, a valid, continuous path P through the trellis might begin and end with a zero state on the trellis. Thus, α(So)=1 when So=0, and α(So)=0 when So≠0.
Similarly, the backward recursion for states is given in equation (8):
                                          β            ⁡                          (                              S                i                            )                                =                                    ∑                              S                                  i                  +                  1                                                      ⁢                                          β                ⁡                                  (                                      S                                          i                      +                      1                                                        )                                            ⁢                              γ                ⁡                                  (                                                            S                                              i                        +                        1                                                              ,                                          S                      i                                                        )                                                                    ,                            (        8        )            where the summation is over all transitions from state Si+1 at time i+1 to state Si at time i which are valid transitions. Similarly, β(SK)=1 when SK=0, and β(SK)=0 when So≠0.
Once the forward and backward recursions for states are calculated, equation (6) is employed to generate the LLR value Li for each user symbol at time i using the relationships of equations (7) and (8). Thus, equation (6) may be re-written as given in equation (9):
                              L          i                =                              log            ⁢                                                            ∑                                      P                    ∈                                          P                      +                                                                      ⁢                                  p                  ⁡                                      (                                          Y                      ⁢                                              |                                            ⁢                      X                                        )                                                                                                ∑                                      P                    ∈                                          P                      -                                                                      ⁢                                  p                  ⁡                                      (                                          Y                      ⁢                                              |                                            ⁢                      X                                        )                                                                                =                      log            ⁡                          (                                                                    ∑                                          S                      +                                                        ⁢                                                            α                      ⁡                                              (                                                  S                          i                                                )                                                              ⁢                                          γ                      ⁡                                              (                                                                              S                            i                                                    ,                                                      S                                                          i                              +                              1                                                                                                      )                                                              ⁢                                          β                      ⁡                                              (                                                  S                                                      i                            +                            1                                                                          )                                                                                                                                  ∑                                          S                      -                                                        ⁢                                                            α                      ⁡                                              (                                                  S                          i                                                )                                                              ⁢                                          γ                      ⁡                                              (                                                                              S                            i                                                    ,                                                      S                                                          i                              +                              1                                                                                                      )                                                              ⁢                                          β                      ⁡                                              (                                                  S                                                      i                            +                            1                                                                          )                                                                                                        )                                                          (        9        )            which is known as the log-MAP algorithm. In equation (9), PεP+ when a continuous path P includes the state at time i corresponding to the user symbol xi=“1” (“ε” is the mathematical term indicating “an element of”). Similarly, PεP− when a continuous path P includes the state at time i corresponding to the user symbol xi=“−1”. Also, in equation (9), a transition between a state pair that are elements of S+ is defined as a transition for a state pair at time i corresponding to the user symbol xi=“1”. A transition between a state pair that are elements of S− is similarly defined as a transition for a state pair at time i corresponding to the user symbol xi=“−1”.
The log-MAP algorithm calculation of the LLR value is sometimes approximated, and one such approximation is the max-log-MAP algorithm. The max-log-MAP algorithm calculates LLR Li(M) at time i as given in equation (10):
                              L          i                      (            M            )                          =                              log            ⁢                                                            ∑                                      P                    ∈                                          P                      +                                                                      ⁢                                  p                  ⁡                                      (                                          Y                      ⁢                                              |                                            ⁢                      X                                        )                                                                                                ∑                                      P                    ∈                                          P                      -                                                                      ⁢                                  p                  ⁡                                      (                                          Y                      ⁢                                              |                                            ⁢                      X                                        )                                                                                ≈                      log            ⁢                                                                                max                                          P                      +                                                        ⁢                                      p                    ⁡                                          (                                              Y                        ⁢                                                  |                                                ⁢                        X                                            )                                                                                                            max                                          P                      -                                                        ⁢                                      p                    ⁡                                          (                                              Y                        ⁢                                                  |                                                ⁢                        X                                            )                                                                                  .                                                          (        10        )            
To simplify the computations, a MAP algorithm (e.g., log-MAP, max-log-MAP) might be modified by substituting A(Si)=log(α(Si), B(Si)=log(β(Si)), and C(Si−1Si)=log(γ(Si−1Si)) into the equations (7), (8), and (9). The forward and backward recursions of the MAP algorithm may be described as in equations (11) and (12):
                              A          ⁡                      (                          S              i                        )                          =                              max                          S                              i                -                1                                              ⁢                      *                          {                                                A                  ⁡                                      (                                          S                                              i                        -                        1                                                              )                                                  +                                  C                  ⁡                                      (                                                                  S                                                  i                          -                          1                                                                    ,                                              S                        i                                                              )                                                              }                                                          (        11        )                                          B          ⁡                      (                          S              i                        )                          =                              max                          S                              i                +                1                                              ⁢                      *                          {                                                B                  ⁡                                      (                                          S                                              i                        +                        1                                                              )                                                  +                                  C                  ⁡                                      (                                                                  S                        i                                            ,                                              S                                                  i                          +                          1                                                                                      )                                                              }                                                          (        12        )            where max*(x, y) is defined as max(x, y)+log((e−|x−y|)+1). Note that equations (11) and (12) may include more than two terms in the max*( ) operator, indicated by the set notation “{ }”, so a max*(x, y, . . . , z) operation may be performed as a series of pairs of max*(•,•) calculations. Max (x, y) is defined as the “max term” and log((e−|x−y|)+1) is defined as the “logarithmic correction term.”